package n3126;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	
	static int [][] list =new int[81*81][2];
	
	static boolean[] visit=new boolean[10000];
	
	static boolean isPrime(int n)
	{
		int mid=(int)Math.sqrt(n);
		for(int i=2;i<=mid;i++)
		{
			if(n%i==0)return false;
		}
		return true;
	}
	static int bfs(int start,int end)
	{
		if(start==end)return 0;
		for(int i=0;i<9999;i++)visit[i]=false;
		int i=0,count=1;
		list[0][0]=start;
		list[0][1]=0;
		visit[start]=true;
		while(i<count)
		{
			int cur=list[i][0];
			int step=list[i][1];
			if(cur==end)return step;
			int a[]=new int[4];
			a[0]=cur/1000;
			a[1]=(cur%1000)/100;
			a[2]=(cur%100)/10;
			a[3]=cur%10;
			for(int k=0;k<10;k++)
			{
				int change;
				if(k!=0) {
					change=k*1000+a[1]*100+a[2]*10+a[3];
					if(change==end)return step+1;
					if(visit[change]==false&&isPrime(change)) {
						list[count][0]=change;
						list[count][1]=step+1;
						visit[change]=true;
						count++;
					}
				}
					change=a[0]*1000+k*100+a[2]*10+a[3];
					if(change==end)return step+1;
					if(visit[change]==false&&isPrime(change)) {
						list[count][0]=change;
						list[count][1]=step+1;
						visit[change]=true;
						count++;
					}
				change=a[0]*1000+a[1]*100+k*10+a[3];
				if(change==end)return step+1;
				if(visit[change]==false&&isPrime(change)) {
					list[count][0]=change;
					list[count][1]=step+1;
					visit[change]=true;
					count++;
				}
				change=a[0]*1000+a[1]*100+a[2]*10+k;
				if(change==end)return step+1;
				if(visit[change]==false&&isPrime(change)) {
					list[count][0]=change;
					list[count][1]=step+1;
					visit[change]=true;
					count++;
				}
			}
			i++;
		}
		
		return -1;
	}
	
	
	/**
	 * @param args
	 */
	public static void main(String[] args) throws Exception{
		// TODO Auto-generated method stub

		BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
		String line=bf.readLine();
		int total=Integer.parseInt(line);
		for(int i=0;i<total;i++)
		{
			line=bf.readLine();
			StringTokenizer st=new StringTokenizer(line);
			int start=Integer.parseInt(st.nextToken());
			int end=Integer.parseInt(st.nextToken());
			int ans=(bfs(start,end));
			if(ans==-1)System.out.println("Impossible");
			else System.out.println(ans);
		}
	}

}
